package Hard;

import Midium.Solution56;

//57.插入区间
public class Solution57 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            int[][] res = new int[1][2];
            res[0][0] = newInterval[0];
            res[0][1] = newInterval[1];
            return res;
        }

        int intervalsCount = 0; //将把原有的这么多个区间合并为1个区间
        //找到合并后区间的left,刚好小于等于newInterval[0]的数
        int left = 0, right = 0;
        int i = 0, j = 0;
        for (i = 0; i < intervals.length; i++) {
            if (intervals[i][0] > newInterval[0]) {
                left = i;
                break;
            }
        }
        left--;

        if (left < -1)
            left = -1;
        else if (left == -1)
            left = 0;
        if (intervals[left][1] < newInterval[0])
            left++;
        System.out.println("left:" + left);
        if (i == intervals.length) {
            if (newInterval[0] > intervals[i - 1][1]) {
                int[][] res = new int[intervals.length + 1][2];
                for (int k = 0; k < intervals.length; k++) {
                    res[k][0] = intervals[k][0];
                    res[k][1] = intervals[k][1];
                }
                res[intervals.length][0] = newInterval[0];
                res[intervals.length][1] = newInterval[1];
                return res;
            }
            left = i - 1;

        }
        //找到合并后区间的right，刚好大于等于newInterval[1]的数
        for (j = left; j < intervals.length; j++) {
            intervalsCount++;
            if (intervals[j][1] == newInterval[1]) {
                right = j;
                break;
            } else if (intervals[j][1] > newInterval[1]) {
                right = j - 1;
                intervalsCount--;
                if (right < left) {
                    if (newInterval[1] < intervals[left][0]) {
                        left = -1;
                        break;
                    }
                    right = left;
                    intervalsCount = 1;
                    break;
                }
                //再判断一下j指向的第一个数是不是正好大于等于newInterval[1]
                if (newInterval[1] >= intervals[j][0]) {
                    right++;
                    intervalsCount++;
                }
                break;
            }
        }
        if (j == intervals.length) {
            if (newInterval[1] >= intervals[intervals.length - 1][0])
                right = intervals.length - 1;
            else
                right = -1;
        }
        //开始构造返回的数组
        if (left == -1) {
            int[][] res = new int[intervals.length + 1][2];
            res[0][0] = newInterval[0];
            res[0][1] = newInterval[1];
            for (int k = 0, l = 1; k < intervals.length; k++, l++) {
                res[l][0] = intervals[k][0];
                res[l][1] = intervals[k][1];
            }
            res = new Solution56().merge(res);

            return res;
        }
        if (right == -1) {
            int[][] res = new int[left + 1][2];
            for (int k = 0; k < left; k++) {
                res[k][0] = intervals[k][0];
                res[k][1] = intervals[k][1];
            }
            res[left][0] = intervals[left][0];
            res[left][1] = newInterval[1];
            return res;
        }
        int[][] res = new int[intervals.length - intervalsCount + 1][2];
        for (int k = 0; k < left; k++) {
            res[k][0] = intervals[k][0];
            res[k][1] = intervals[k][1];
        }
        res[left][0] = intervals[left][0] < newInterval[0] ? intervals[left][0] : newInterval[0];
        res[left][1] = newInterval[1] > intervals[right][1] ? newInterval[1] : intervals[right][1];
        for (int k = left + 1, l = right + 1; l < intervals.length; k++, l++) {
            res[k][0] = intervals[l][0];
            res[k][1] = intervals[l][1];
        }
        return res;


    }

    public static void main(String[] args) {
        Solution57 s = new Solution57();
//        int[][] insert = s.insert(new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, new int[]{4, 8});
        int[][] insert = s.insert(new int[][]{{3, 5}, {12, 15}}, new int[]{6, 6});
        for (int[] arr : insert) {
            System.out.print("[");
            for (int a : arr) {
                System.out.print(a + " ");
            }
            System.out.println("],");
        }
    }


}
